package com.wtgroup.demo.leetcode.q012_整数转罗马数字;

import com.wtgroup.demo.common.util.RandomUtil;

/**
 * 贪心方式
 *
 * @author dafei
 * @version 0.1
 * @date 2021/3/28 19:52
 */
public class S_LC_M1 {

    public static void main(String[] args) {
        // int[] inputs = {3, 4, 9, 58, 1994, 999, 3999};
        int[] inputs = RandomUtil.randomArray(1000, 1, 4000);
        S_LC_M1 exe = new S_LC_M1();
        for (int input : inputs) {
            // System.out.println(exe.intToRoman(input));
            String res1 = exe.intToRoman(input);
            // String res2 = exe.intToRoman_2(input);
            // if (res1 != res2) {
            //     System.out.println(input);
            //     System.out.println(res1);
            //     System.out.println(res2);
            //     break;
            // }
        }
    }

    /**
     * 贪心方式
     * <p>
     * 从大到小排序映射.
     * 尽大的先用.
     */

    static int[] NUMS = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    static String[] ROMANS = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    public String intToRoman(int num) {
        // 消耗到此数字值时, 下次必然从此处开始, 而不用从头开始
        String ans = "";
        for (int i = 0; i < NUMS.length && num > 0; i++) {
            while (num >= NUMS[i]) {
                ans += ROMANS[i];
                num -= NUMS[i];
            }
        }

        return ans;
    }
}
